// 76.最小覆盖子串

package LeetcodeHot100;


public class Solution076 {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0)
            return "";
        // 记录需要的字符和数量
        int[] needs = new int[128];
        for (char c : t.toCharArray()) {
            ++needs[c];
        }

        int left = 0, right = 0; // 左右边界
        int size = Integer.MAX_VALUE; // 记录最小窗口的大小
        int start = 0; // 记录最小窗口的开始位置
        int count = t.length(); // 记录需要字符的个数

        while (right < s.length()) {
            // 判断有边界的字符是否是需要的字符
            if (needs[s.charAt(right)] > 0)
                count--;
            // 将右边界的字符加入窗口中
            --needs[s.charAt(right)];
            if (count == 0) { // 如果窗口已经包含所有需要的字符，则开始收缩左边界
                while (left < right && needs[s.charAt(left)] < 0) { // 左边的字符是多余的字符
                    needs[s.charAt(left)]++;
                    left++;
                }
                // 判断窗口大小，记录窗口大小和初始位置
                if (right - left + 1 < size) {
                    size = right - left + 1;
                    start = left;
                }
                // 左边界收缩，寻找下一个符合要求的窗口
                needs[s.charAt(left)]++;
                left++;
                count++; // 此时左边界的字符一定是需要的字符
            }
            right++;
        } // while

        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}
